<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Quiz - Strings and Arrays</title>
  <meta
 content="C++ Tutorial: Quiz - Strings and Arrays"
 name="description" />
  <meta
 content="C++ Tutorial, Quiz - Strings and Arrays, Interview Questions"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
|<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
| <a href="../python/pytut.html">Python</a> 
| <a href="../CSharp/.netframework.html">C#</a>
| <a href="../forums.html">Forums</a> 
| <a href="../VisualBasicSQL/introduction.html">Visual Basic</a>
</div>
</div>


<div id="contenttext">
<br />
<br />
<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>


<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>

<br />
<br />

<br />
<br />

<div style="padding: 10px;"><span class="titletext">C++ Tutorial <br />
Quiz - Strings and Arrays</span></div>

<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<br />
<br />
<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="SubList">List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a></li> 
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II - void*, Pointer/Array, and Pointer to Pointer</a></li>
   <li><a href="pointers3.html">Pointers III - Pointer to Function, Null Pointer</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>
</div>
<br />

<br />
<img src="images/quiz/KumKangSan.png" alt="KumKangSan"/>
<br />
<br />
<br />

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="SubList">Codes Listed on This Page</div>
<ul>
   <li> <a href="#uniquecharacters">Unique Characters</a> </li>
   <li> <a href="#matrix_rotation">Rotating a Matrix by 90 Degrees</a> 
</li>
   <li><a href="#anagram">Are Two Strins Anagram?</a> </li>
   <li><a href="#replacing_string">Replacing Spaces of a String</a></li>
   <li><a href="#remove_string">Remove Duplicate Strings</a></li>

   <li><a href="#rotatin_string">Rotating String (Substring)</a></li>
   <li><a href="#zero_matrix">Zero Matrix</a></li>
   <li><a href="#removingchars">Removing Characters from a String</a></li>
   <li><a href="#reversewords">Reverse a String and Words</a></li>
   <li><a href="#stringintersection">Intersection of Two Character Strings - Filtering</a></li>
   <li><a href="#baseconversion">Base Conversion</a></li>
</ul>
</div>
<br />

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle" id="string_array">Codes - Strings and Arrays</div>
<p>Strings and arrays are closely related. In some way, a string is really just an array of characters. Lots of string manipulation problems we encounter are therefore based on our understanding of array data types because strings and character arrays are essentially identical in C/C++.</p>
<p>Codes listed here are some solutions to the problems. Some of them could be given  as interview questions.</p>
<br />

<div class="subtitle_2nd" id="arrays">Arrays</div>
<p>An array is a sequence of variables of the same type arranged contiguously in a block of memory. </p>
<p>Like a linked list, an array provides an essentially linear form of storage, but its properties are significantly different. In a linked list, lookup is always an O(<i>n</i>) operation, but array lookup is O(1) as long as we know the index of the element.</p>
<p>The price for this improved lookup is significantly decreased efficiency in the insertion and deletion of data in the middle of the array. Because an array is essentially a block of memory, it's not possible to create or eliminate storage between any two elements as it is with a linked list. Instead, we must physically move data within the array to make room for an insertion or to close the gap left by a deletion.</p>
<p>Arrays are not dynamic data structures. They have a finite, fixed number of elements. Memory must be allocated for every element in an array. Arrays are best used when we know how many elements we need to store before the program executes. When the program needs a variable amount of storage, the size of the array imposes an arbitrary limit on the amount of data that can be stored. Making the array large enough so that the program always operates below the limit doesn't solve the problem. We could waste memory or we may be short of memory to handle the largest data sizes possible.</p>
<p>Dynamic arrays are arrays that can change size to store as much or as little data as necessary. But it is important to know that most dynamic array implementations use static array internally. A static array cannot be resized, so dynamic arrays are resized by allocating a new array of the appropriate size, copying every element from the old array into the new array, and freeing the old array. This is an expensive operation that must be done as infrequently as possible.</p>
<p>In most cases, an array name is equivalent to a pointer constant (i.e., char *const ptr) to the first element of the array. This means that we can't initialize the element of one array with another array using a simple assignment:</p>
<pre>
arrayA = arrayB;
</pre>
<p>This will give us compile error because <strong>arrayA</strong> is not an <strong>lvalue</strong>. The assignment is interpreted as an attempt to make <strong>arrayA</strong> refer to the same area of memory as <strong>arrayA</strong>. If <strong>arrayA</strong> jas been declared as an array, this causes a compile error bacause we can't change the memory location to which <strong>arrayA</strong> refers. Top copy <strong>arrayB</strong> to <strong>arrayA</strong>, we have to write a loop that does an element by element assignment or use a library function such as <strong>memcpy()</strong> that does the copying for us.</p>
<p>In C/C++, the compiler tracks only the <strong>location</strong> of arrays, not their <strong>size</strong>. The programmer is responsible for tracking array sizes, and there is no bounds checking on array accesses. So, the language won't complain if we store something in the twentieth element of a ten-element array. Writing outside  of the bounds of an array will probably overwrite some other data structure, leading to all manner of curious and difficult-to-find bugs. </p>
<br />

<div class="subtitle_2nd" id="strings">Strings</div>
<p>Strings are sequence of characters. </p>
<ul>
<li> <strong>C</strong> <br />
A C string is nothing more than a <strong>char</strong> array. Just as C doesn't track the size of arrays, it doesn't track the size of strings. Instead, the end of the string is marked with a null character, represented in the language as <strong>'\0'</strong>. The null character is sometimes referred to as <strong>NULLCHAR</strong>. Using <strong>NULL</strong> is incorrect because <strong>NULL</strong> is specifically reserved for use with pointers. The character array must have room for the terminator: A 10-character string requires an 11-character array. This scheme makes finding the length of the string an O(<i>n</i>) operation instead of O(1). So, <strong>strlen()</strong> must scan through the string until it finds th ends.</p>
<p>For the same reason that we can't assign one C array to another, we cannot copy C string using <strong>=</strong> operator. Instead, we generally use the <strong>strcpy</strong> function.</p>
<p>It is often convenient to read or alter a string by addressing individual characters of the array. If we change the length of a string in this manner, we should make sure we write a null character after the new last character in the string, and that the character array we are working in is large enough to accommodate the new string and terminator. It's easy to truncate a C string: Just place a null character immediately after the new end of the string.</li>
<li><strong>C++</strong><br />
C-style strings can be used with C++. However, the preferred approach is to use the <strong>string</strong> class from the standard libraries whenever possible. The <strong>string</strong> class is a specialization of the <strong>basic_string</strong> template class using a <strong>char</strong> data type. If we want to create strings that store Unicode values, we can define a new variant of <strong>basic_string</strong> based on the <strong>wchar_t</strong> which is wide character type.<br />
The string class is very well integrated into the C++ standard libraries. We can use them with streams and iterators. In addition, C++ strings are not null-terminated, so they can store null bytes, unlike C strings. Multiple copies of the same string share the same underlying buffer whenever possible. But because a string is mutable, new buffers are created as necessary. </li>
</ul>

<br />
<br />

<div class="subtitle_2nd" id="uniquecharacters">Unique Characters</div>
<p>Codes to find out if a string has all unique characters.</p>
<p><strong>Method A</strong> <br />
Using the fact that ASCII characters are treated as an integer. So, we index the 256 array using characters from the string. Each time we indexing the array, we increment the value of that element. The value itself is the counter for that character. </p>
<pre>
#include &lt;iostream&gt;

using namespace std;

char *uniqueCharsA(char *s)
{
	int arr[256]={0};

	while(*s) {
		arr[*s]++ ;
		if(arr[*s] > 1) return "not unique";	
		s++;
	}
	return "unique";	
}

int main()
{
	cout << uniqueCharsA("abcdefghijkl") << endl;
	cout << uniqueCharsA("abcdefghiiii") << endl;
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
unique
not unique
</pre>
<br />
<br />
<p><strong>Method B</strong><br />
Using a bit vector. This is not a universal method. I mean it would only work for certain range of ASCII characters. For example, the characters in the string should be all a-z. <br />
So, in this case, we have only one 32-bit integer to store the characters. But that's enough to store 26 character from a to z.</p>
<pre>
#include &lt;iostream&gt;
using namespace std;

char *uniqueCharsB(char *s)
{
	int bit = 0;

	while(*s) {
		int i = *s - 'a';
		if( (bit & (1 << i)) > 0 ) return "not unique";
		bit |= (1 << i);
		s++;
	}
	return "unique";	
}

int main()
{
	cout << uniqueCharsB("adhijkl") << endl;
	cout << uniqueCharsB("adhiiii") << endl;
	return 0;
}
</pre>
<p>Output is the same as the previous method:</p>
<pre>
unique
not unique
</pre>
<p>If it's <strong>a</strong>, the bit vector becomes</p>
<pre>
0000............001
</pre>
<p>If the next character is <strong>b</strong>, the second bit of the bit vector is set to 1</p>
<pre>
0000............011
</pre>
<p>If the next character is <strong>c</strong>, the third bit of the bit vector is turned on</p>
<pre>
0000............111
</pre>
<p>So, when we have a character <strong>d</strong> as the next character, the pattern of the <strong>bit</strong> vector becomes </p>
<pre>
0000...........1111
</pre>
<p>and so on.</p>
<p>As a specific example when the string is <strong>"adhiiii"</strong>, if it's a character <strong>d</strong>, the bit vector at that point is:</p>
<pre>
0000000000000000001
</pre>
<p>since we had <strong>a</strong> for the previous set of characters. The bit vector will be bit-and (&) with </p>
<pre>
0000000000000001000
</pre>
<p>resulting 0, so the while loop continues...</p>
<p>When we see second <strong>i</strong> of the second input, the bit pattern is</p>
<pre>
0000......<font color="red">1</font>10001001
</pre>
<p>because we've seen <strong>a, d, h</strong>, and <strong>i</strong> already.</p>
<p>It will be Ending with</p>
<pre>
0000000000<font color="red">1</font>00000000
</pre>
<p>Since we had <strong>i</strong> before, the <strong>i-th</strong> bit of the bit vector is on, we have duplicate characters.</p>
<br />
<br />


<div class="subtitle_2nd" id="matrix_rotation">Matrix Rotation</div>
<p>Rotating <strong>N x N</strong> matrix in place.<br />
For example, an image represented by an <strong>N X N</strong> matrix, where each pixel in the image is 4 bytes. We want to rotate the image by 90 degrees.</p>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;

using namespace std;

const int N = 5;

void makeZero(int a[][N])
{
	int i,layer;
	int first, last;
	int top, topleft;

	for(layer = 0; layer < N/2; layer++) {
		first = layer + 1;
		last = N - 1 - layer;
		
		// edges
		for(i = first; i < last; i++) {
			// saving top  
			top = a[layer][i];		
			// left -> top  
			a[layer][i] = a[N-1-i][layer];
			// bottom -> left  
			a[N-1-i][layer] = a[N-1-layer][N-1-i];
			// right -> bottom  
			a[N-1-layer][N-1-i] = a[i][N-1-layer];
			// saved top -> right  
			a[i][N-1-layer] = top;

		}
		// corners
		topleft = a[layer][layer];
		// lowerleft -> topleft
		a[layer][layer] = a[N-1-layer][layer];
		// bottomright -> lowerleft
		a[N-1-layer][layer] = a[N-1-layer][N-1-layer];
		// topright -> bottomright
		a[N-1-layer][N-1-layer] = a[layer][N-1-layer];
		// topleft ->topright
		a[layer][N-1-layer] = topleft;
	}
}

int main()
{
	int a[5][N]={{1,2,3,4,5},
				{6,7,8,9,10},
				{11,12,13,14,15},
				{16,17,18,19,20},
				{21,22,23,24,25},
				};

	/* passing array of N rows */
	makeZero(a);

	for (int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) 
			cout << setw(3) << a[i][j];
		cout << endl;
	}
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
 21 16 11  6  1
 22 17 12  7  2
 23 18 13  8  3
 24 19 14  9  4
 25 20 15 10  5
</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="anagram">Are Two Strins Anagram?  </div>
<p>A routine to decide if two strings are anagrams or not.</p>
<pre>
#include &lt;iostream&gt;
using namespace std;

bool anagram(char s1[], char s2[])
{
	int bit[256] = {0};
	if(s1 == NULL || s2 == NULL) return false;

	int len = strlen(s1);
	int len2 = strlen(s2);
	if(len != len2) return false;

	for(int i = 0; i < len; i++) {
		bit[s1[i]]++;
	}

	for(int i = 0; i < len; i++) {
		bit[s2[i]]--;
	}

	for(int i = 0; i < 256; i++) {
		if(bit[i] != 0) return false;
	}
	return true;
}

int main()
{
	char *s1 = "hamlet";
	char *s2 = "letham";
	char *s3 = "latham";

	if(anagram(s1,s2))  
		cout << "Anagram\n";
	else
		cout << "Not an anagram\n";

	if(anagram(s1,s3)) 
		cout << "Anagram\n";
	else
		cout << "Not an anagram\n";
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
Anagram
Not an anagram
</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="replacing_string">Replacing Spaces of a String</div>
<p>The following example is replacing spaces in a string "<strong>Replace spaces with special characters</strong>" with "<strong>$99</strong>"</p>
<pre>
#include &lt;iostream&gt;
using namespace std;


/* Replacing spaces with "$99" */

char *replacingSpaces(char s[])
{
	if(s == NULL ) return false;

	int i, last = 0, spaceCount = 0;
	char *sp = "$99";

	int lensp = strlen(sp);
	int len = strlen(s);

	for(i = 0; i < len; i++) {
		if(s[i] == ' ') spaceCount++;
	}
	if(spaceCount == 0) return s;

	char *newStr = (char *)malloc(spaceCount*(lensp-1) + len + 1);

	for(i = 0; i < len; i++) {
		if(s[i] != ' ') {
			newStr[last++] = s[i];
		}
		else {
			newStr[last++] = sp[0];
			newStr[last++] = sp[1];
			newStr[last++] = sp[2];
		}
	}
	newStr[last++]='\0';
 
	return newStr;
}

int main()
{
	char s[60] = "Replace spaces with special characters";
	cout << replacingSpaces(s) << endl;
	return 0;
}
</pre>
<p>Output is:</p>
<pre>Replace$99spaces$99with$99special$99characters</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="remove_string">Remove Duplicate Strings</div>
<p>A code to remove the duplicate characters in a string without using any additional buffer (no extra copy of the array).</p>
<p><strong>Example A</strong>
<pre>
#include &lt;iostream&gt;
using namespace std;

void removeDuplicateA(char s[])
{
	int i,j,last = 1;
	if(s == NULL) return;
	int len = strlen(s);
	if(len < 2) return;

	for(i = 1; i < len; i++) {
		for(j = 0; j < last; j++) {
			if(s[i] == s[j]) break;
		}
		if(last == j) 
			s[last++] = s[i];
	}
	s[last] = '\0';
}

int main()
{
	const int M = 6;
	char *s[M] = {strdup("abcde"),
		        strdup("aaaaa"),
		        strdup("ababa"),
                      strdup("abcdefabcdefg"),
		        strdup(""),
                      NULL
                      };
	for(int i = 0; i < M; i++) {
		if(s[i])cout << "old: " << s[i] << endl;
		removeDuplicateA(s[i]);
		if(s[i])cout << "new: " << s[i] << endl;
	}
	return 0;
}
</pre>
<p>Output from the run is:</p>
<pre>
old: abcde
new: abcde
old: aaaaa
new: a
old: ababa
new: ab
old: abcdefabcdefg
new: abcdefg
old:
new:</pre>
<br />
<br />
<p><strong>Example B</strong></p>
<p>This method requires additional memory, though.</p>
<pre>
#include &lt;iostream&gt;
using namespace std;

void removeDuplicateB(char s[]) 
{
	int last = 0;
	int c[256]={0};
	if(s == NULL) return;
	if(strlen(s) < 2) return;
	for(int i = 0; i < strlen(s); i++) {
		if(c[s[i]] < 1) {
			c[s[i]]++;
			s[last++] = s[i];
		}	
	}
	s[last]='\0';
}
int main()
{
	const int M = 6;
	char *s[M] = {strdup("abcde"),
		        strdup("aaaaa"),
		        strdup("ababa"),
                      strdup("abcdefabcdefg"),
		        strdup(""),
                      NULL
                      };
	for(int i = 0; i < M; i++) {
		if(s[i])cout << "old: " << s[i] << endl;
		removeDuplicateB(s[i]);
		if(s[i])cout << "new: " << s[i] << endl;
	}

	for(int i = 0; i < M-1; i++) free(s[i]);
	return 0;
}
</pre>
<br />
<p>Output is: </p>
<pre>
old: abcde
new: abcde
old: aaaaa
new: a
old: ababa
new: ab
old: abcdefabcdefg
new: abcdefg
old:
new:</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="rotatin_string">Rotating Strings</div>
<p>Given two strings, <strong>s1</strong> and <strong>s2</strong>, this code is checking if <strong>s2</strong> is a rotation of <strong>s1</strong> using a call to a routine which checks if one word is a substring of another. In this example, <strong>strstr()</strong> is used.</p>
<pre>
#include &lt;iostream&gt;
using namespace std;

bool substring(char s1[], char s2[])
{
	bool ret = false;
	if(s1 == NULL || s2 == NULL) return ret;
	if(strlen(s2) == 0) return ret;

  	char *s3 = (char *)malloc(strlen(s1)*2+1);
 	strcpy(s3,s1);
	strcat(s3,s1);

 	if(strstr(s3,s2)) ret = true;
	free(s3);
	return ret;
}

int main()
{
	char *s1 = "apple";
	char *s2 = "leapp";  /* rotation */
	char *s3 = "laepp";  /* not a rotation */
	char *s4 = "pplea";  /* rotation */

	if(substring(s1,s2))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	if(substring(s1,s3))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	if(substring(s1,s4))  
		cout << "Substring\n";
	else
		cout << "Not a substring\n";

	return 0;
}
</pre>
<br />
<p>Output from the run:</p>
<pre>
Substring
Not a substring
Substring
</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="zero_matrix">Zero Matrix</div>
<p>Write an algorithm such that if an element in an M x N matrix is 0, its entire row and column is set to 0.</p>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;

using namespace std;

const int M = 5, N = 4;

void makeZero(int a[][N])
{
	int row[M] = {0};
	int col[N] = {0};

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			if(a[i][j] == 0) {
				row[i] = 1;
				col[j] = 1;
			}
		}
	}

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			if(row[i] == 1 || col[j] == 1) {
				a[i][j] = 0;
			}
		}
	}
}

int main()
{
	int a[M][N]={{1,2,3,4},
			{5,6,7,8},
			{9,0,11,12},
			{13,14,15,16},
			{17,18,19,0},
			};
	/* passing array of M rows */
	makeZero(a);

	for (int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			cout << setw(3) << a[i][j];
		}
		cout << endl;
	}
	return 0;
}
</pre>
<br />
<p>Output from the run:</p>
<pre>
  1  0  3  0
  5  0  7  0
  0  0  0  0
 13  0 15  0
  0  0  0  0
</pre>
<br />
<br />
<br />


<div class="subtitle_2nd" id="removingchars">Removing Characters from a String</div>
<p>The code below removes specified characters ("aeiouAEIOU") from a string ("Ludwig Van Beethoven").</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

void removeChars(char *inStr, char *rmvStr)
{
	int i,j = 0;
	char flag[256] = {0};
	while(*rmvStr) flag[*rmvStr++]++;
	
	for(i = 0; i < strlen(inStr); i++) {
		if(flag[inStr[i]] == 0) {
			inStr[j++] = inStr[i];
		}
	}
	inStr[j] = '\0';
}

int main()
{
	char *input = strdup("Ludwig Van Beethoven");
	char *remove = "aeiouAEIOU";
	cout << "In: " << input << endl;
	cout << "removing " << remove << "..." << endl;
	removeChars(input,remove);
	cout << "Out: " << input << endl;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
In: Ludwig Van Beethoven
removing aeiouAEIOU...
Out: Ldwg Vn Bthvn
</pre>
<br />
<br />


<div class="subtitle_2nd" id="reversewords">Reverse a String and Words</div>
<p>The following code reverse words using spaces as delimiters. <br />
First, it reverses all strings. <br />
For example, convert "I am a boy" to "yob a ma I".<br />
 Then, we reverse each word one by one. So, the complexity of this algorithm is <i>O(n)</i>.</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

/* reverse the characters in a string */
void reverseString(char *str, int start, int end)
{
	char c;
	for(int i = start, j = end; i <= j; i++, j--) {
		c = str[i];
		str[i] = str[j];
		str[j] = c;	
	}
}

/* reverse the words */
void reverseWords(char *words)
{
	int start = 0, end;

	reverseString(words, 0, strlen(words)-1);
	cout << "Intermediate string: " << words << endl;

	/* find a word using a space as a delimiter, 
	   and reverse it again */
	for(int i = 0; i <= strlen(words); i++) {
		if(words[i] == ' ' || words[i] == '\0') {
			end = i - 1 ;
			reverseString(words, start, end);
			start = i + 1;
		}
	}
}

int main()
{
	char *myStr = strdup("Ludwig Van Beethoven");

	cout << "In: " << myStr << endl;
	reverseWords(myStr);
	cout << "Out: " << myStr << endl;

	free(myStr);

	return 0;
}
</pre>
<p>Output from the run is:</p>
<pre>
In: Ludwig Van Beethoven
Intermediate string: nevohteeB naV giwduL
Out: Beethoven Van Ludwig
</pre>
<br />
<br />


<div class="subtitle_2nd" id="stringintersection">Intersection of Two Character Strings - Filtering</div>
<p><strong>Q:</strong> Write a function <strong>f(a, b)</strong> which takes two character string arguments and returns a string containing only the characters found in both strings in the order of <strong>a</strong>.</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

char *fn(char* st1, char* st2)
{
	char *retString = (char*)malloc(strlen(st1));
	char c[256] = {0};
	while(*st2) c[*st2++]++;

	int last = 0;
	while(*st1) {
		if(c[*st1]-- > 0) 
			retString[last++] = *st1;
		st1++;
	}
	retString[last]='\0';
	return retString;
}

int main()
{
	char* a = "stroustrup";
	char* b = "programmings";
	cout << "a = " << a << " b = " << b << endl;
	char *str = fn(a,b);
	cout << "str =" << str << endl;
	free(str);
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
a = stroustrup b = programmings
str =srorp
</pre> 
<br />
<br />


<div class="subtitle_2nd" id="baseconversion">Base Conversion</div>
<p>Question: Given a series A,B,C .......Z, AA, AB,AC,AD....AZ,BA,BB...BZ,CA....(Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series. & also vice versa if given string prints its corrsponding string...e.g given AC then its interger is 29 & given 40774 its string value is ABZ..</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

int columnNumber(char *s)
{
	int base = 26;
	int res = 0;
	int digit = 0;
	for(int i = 0; i < strlen(s); i++) {
		res = res *base + s[i]-'A' + 1 ; 
	}
	return res;
}

void reverse(char *s)
{
	int i,j, temp;
	int len = strlen(s);
	for(i = 0, j = len-1; i < j; i++, j--) {
		temp = s[j];
		s[j] = s[i];
		s[i] = temp;
	}
	s[len] = '\0';
}

void columnLabel(int n, char label[])
{
	int base = 26;
	int digit = 0;
	
	while(n > 0) {	
		label[digit++] = (char)((n-1)%base+'A');
		n = (n-1) / base ;
	}
	label[digit]='\0';
	reverse(label);
}

int main()
{
	char *str ;
	char label[10];
	int n;
	str = "Z";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ZZ";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ZZZ";
	cout << str << " = " << columnNumber(str) << endl;
	str = "ABC";
	cout << str << " = " << columnNumber(str) << endl;

	n = 26;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 702;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 18278;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	n = 731;
	columnLabel(n, label);
	cout << n << ": " << label << endl;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
Z = 26
ZZ = 702
ZZZ = 18278
ABC = 731
26: Z
702: ZZ
18278: ZZZ
731: ABC
</pre>
<br />
<br />


<div class="subtitle_2nd" id="stringfile">String & File</div>
<p>Write a function that sums up integers from a text file, one int per line. </p>
<pre>
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;sstream&gt;
#include &lt;string&gt;

using namespace std;

int main() {

	int nn, sum = 0;
	string line;

	ifstream myFile("myInput.txt", ios_base::in); 
	while (getline(myFile,line)) {
		stringstream ss(line);
	 	ss >> nn;
		sum += nn;
	}
	cout << sum << endl;
        return 0;
}
</pre>
<p>The input file is:</p>
<pre>
1
2
..
9 
10
</pre>
<p>Output is the sum of 1,2,....,9,10 which is 55. </p>
<br />
<br />




<p>Additional codes related to string manipulation are here:</p>
<ul>
   <li> <a href="smallprograms.html#strlen">int strlen(const char *)</a> </li>
   <li><a href="smallprograms.html#strcpy">char* strcpy(char *, const char*)</a> </li>
   <li><a href="smallprograms.html#memcpy">void * memcpy ( void * destination, const void * source, size_t sz)</a> </li>
   <li><a href="smallprograms.html#memmove">void *memmove(void *dest, const void *src, size_t sz)</a> </li>
   <li><a href="smallprograms.html#memset">void * memset ( void * destination, int source, size_t sz )</a></li> 
   <li><a href="smallprograms.html#str2int">Converting String to Integer (atoi())
</a></li> 
   <li><a href="smallprograms.html#int2str">Converting Integer to String (itoa())</a></li> 
   <li><a href="smallprograms.html#atof">ASCII String to Float - atof()</a></li> 
   <li><a href="smallprograms.html#strreverse">Reversing a String</a></li> 
   <li><a href="smallprograms.html#nonrepeata">Finding the First Un-repeating (Non-repeating) Character - A</a></li> 
   <li><a href="smallprograms.html#nonrepeatb">Finding the First Un-repeating (Non-repeating) Character - B</a></li> 
</ul>
<br />
<br />

<img src="images/quiz/DoBongSan.png" alt="DoBongSan"/>
<br />
<br />
<br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a></li> 
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>

<br />
<br />
<div id="rightpanel">
<div align="center">
</div></div>
<br />

<br />
</div>

<br />
<br />
<br />



<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2011 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a></div>
</div>
</div>
</body>
</html>

